package src.CodeTop;

/**
 * 删除链表的倒数第N个结点
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 *
 * 进阶：你能尝试使用一趟扫描实现吗？
 *
 *  
 *
 * 示例 1：
 *
 *
 * 输入：head = [1,2,3,4,5], n = 2
 * 输出：[1,2,3,5]
 * 示例 2：
 *
 * 输入：head = [1], n = 1
 * 输出：[]
 * 示例 3：
 *
 * 输入：head = [1,2], n = 1
 * 输出：[1]
 *
 */

public class _19RemoveNthNodeFromEndOfList {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int n = 2;
        ListNode head = TestListNode.generateLinkedList(5, arr);
        ListNode target = removeNthFromEnd1(head, n);
        TestListNode.showLinkedList(target);
    }

    /**
     * 快慢指针法
     * @param head 头结点
     * @param n 倒数第k
     * @return 头结点
     */
    public static ListNode removeNthFromEnd1(ListNode head, int n) {
        // 定义虚头
        ListNode virNode = new ListNode(0);
        // 将虚头连接到原链表上
        virNode.next = head;
        // 定义快慢指针
        ListNode slow = virNode;
        ListNode fast = head;
        // 快指针先走n步
        for (int i = 0 ; i < n ; i++) {
            fast = fast.next;
        }
        // 此时快慢指针一起走
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        // 解开当前结点的下一个结点
        slow.next = slow.next.next;
        // 返回虚头的下一个结点
        return virNode.next;
    }
}
